#define MAX_NODE_SIZE 10001
#define MAX(a, b) ((a) > (b) ? (a) : (b))

void dfs(int *res, int *pos, struct TreeNode* root, int curHeight) {
    if (curHeight == *pos) {
        res[(*pos)++] = root->val;
    } else {
        res[curHeight] = MAX(res[curHeight], root->val);
    }
    if (root->left) {
        dfs(res, pos, root->left, curHeight + 1);
    }
    if (root->right) {
        dfs(res, pos, root->right, curHeight + 1);
    }
} 

int* largestValues(struct TreeNode* root, int* returnSize) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    int *res = (int *)malloc(sizeof(int) * MAX_NODE_SIZE);
    *returnSize = 0;
    dfs(res, returnSize, root, 0);
    return res;
}
